package com.test.daily.leetcode.y2022.m05.day0518.v06;

/**
 * @descriptions: CountSorted
 * @author: Tom
 * @date: 2022/5/18 下午 04:20
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{2,3,4,5,6,1,2,4,5,6,2,3,1};
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
    }
    public static void countSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int[] buckets = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            buckets[arr[i]]++;
        }
        int i = 0;
        for (int j = 0; j < buckets.length; j++) {
            while(buckets[j]-- > 0){
               arr[i++] = j;
            }
        }
    }
}
